package com.thread.comm;

import java.util.Stack;

/** 二叉树
 * Created by daniel on 15-8-22.
 */
public class MyBinaryTree {
//    开始的时候只有根节点
    private TreeNode root=null;

    /*
     * 在构造函数中创建根节点
     */
    public MyBinaryTree(){
        root=new TreeNode(1,"root(A)");
    }

    /**
     * 构造一棵二叉树
     *               A
     *            /     \
     *           B       C
     *         /   \    /
     *        D     E  F
     *          \
     *           G
     */
    public void createBTree(){
        TreeNode newNodeB=new TreeNode(2,"B");
        TreeNode newNodeC=new TreeNode(3,"c");
        TreeNode newNodeD=new TreeNode(4,"D");
        TreeNode newNodeE=new TreeNode(5,"E");
        TreeNode newNodeF=new TreeNode(6,"F");
        TreeNode newNodeG=new TreeNode(7,"G");
        root.leftChild=newNodeB;
        root.rightChild=newNodeC;
        root.leftChild.leftChild=newNodeD;
        root.leftChild.rightChild=newNodeE;
        root.leftChild.leftChild.rightChild=newNodeG;
        root.rightChild.leftChild=newNodeF;
    }
//    返回根节点
    public TreeNode getRoot(){
        return root;
    }
    //返回高度
    public int getHeight(TreeNode subTree){
        return height(subTree);
    }
    //计算高度
    private int height(TreeNode node) {
        if(node==null)
        return 0;
        else {
            int l=height(node.leftChild);
            int r=height(node.rightChild);
            return (l<r)?(r+1):(l+1);
        }
    }
    //返回节点个数
   public int getSize(TreeNode subTree){
       return size(subTree);
   }
   //计算节点个数
    private int size(TreeNode node) {
        if(node==null)
            return 0;
        else{
            return 1+size(node.leftChild)
                    +size(node.rightChild);
        }
    }

    /**
     * 返回某节点的父亲节点
     * @param subTree
     * @param node
     * @return
     */
    public TreeNode getParent(TreeNode subTree,TreeNode node){
        if(subTree==null)
            return null;
        if(subTree.leftChild==node || subTree.rightChild==node)
            return  subTree;
        TreeNode p;
//        先在左子树中找，找不到再去右子树中找
        if((p=getParent(subTree.leftChild,node))!=null)
            return p;
        else
            return getParent(subTree.rightChild,node);
    }
//    前序递归遍历
    public void preOrder(TreeNode subTree){
        if(subTree==null)
            return;
        else{
            visit(subTree);
            preOrder(subTree.leftChild);
            preOrder(subTree.rightChild);
        }
    }
//    中序递归遍历
    public void inOrder(TreeNode subTree){
        if(subTree==null)
            return;
        else{
            inOrder(subTree.leftChild);
            visit(subTree);
            inOrder(subTree.rightChild);
        }
    }
//    后序递归遍历
    public void postOrder(TreeNode subTree){
        if(subTree==null)
            return;
        else{
            postOrder(subTree.leftChild);
            postOrder(subTree.rightChild);
            visit(subTree);
        }
    }
//非递归前序遍历，用栈实现
    public void nonRecPreOrder(TreeNode subTree){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode p=subTree;
        while(p!=null||stack.size()>0){
//            先把左节点全部入栈,这些左节点将作为根节点
            while(p!=null){
                visit(p);
                stack.push(p);
                p=p.leftChild;
            }
//            没有左节点了，就弹栈，将弹出的节点的右孩子节点压栈
            if(stack.size()>0){
                p=stack.pop();
                p=p.rightChild;
            }
        }
    }
//    非递归中序遍历
    public void nonRecInOrder(TreeNode subTree){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode p=subTree;
        while(p!=null || stack.size()>0){
            while(p!=null){
                stack.push(p);
                p=p.leftChild;
            }
            if(stack.size()>0){
                p=stack.pop();
                visit(p);
                p=p.rightChild;
            }
        }
    }
//    非递归后序遍历
    public void nonRecPostOrder(TreeNode subTree){
        Stack<TreeNode> stack=new Stack<>();
        TreeNode p=subTree;
        TreeNode node=null;
        while(p!=null){//处理一个根节点
//            把这个根节点的所有左孩子都压入栈中，从上到下
//            这里最后一个节点没有压栈
            for(;p.leftChild!=null;p=p.leftChild)
                stack.push(p);
//            开始依次处理栈中的根节点
//            当前节点不为空且没有右孩子或者右孩子已经访问过，根据后序遍历的定义，可以直接访问该根节点了
            while(p!=null&&p.rightChild==null||p.rightChild==node){
                visit(p);
//                记录一下，因为如果弹栈之后遇到了右孩子不为空的根节点，就会先把这个根节点再次压回栈中，然后把它的右孩子节点也压入栈中
//                这样，栈中，右孩子节点就在根节点的上面紧挨着根节点，访问的时候，也是访问完右孩子就直接访问它
//                所以，判断某个右孩子不为空的根节点孩子是否被访问过，就看node==rightChild与否
                node=p;
                if(stack.size()==0)
                    return;
//                栈不为空,继续弹出处理根节点
                p=stack.pop();
            }
//           这里的p是右孩子没有被访问过的根节点,把这个已经在while循环中弹出的根节点先压回栈中
            stack.push(p);
//            然后得到它的右孩子，继续新的一支的压栈，弹栈，访问处理
//            处理完它的右孩子自然就会处理栈中刚刚压回的处于下一个位置的根节点
            p=p.rightChild;
        }
    }
    /**
     * 访问节点
     * @param node
     */
    private void visit(TreeNode node){
        node.isVisited=true;
        System.out.println("访问"+node.data+",key="+node.key);
    }

    /**
     * 节点数据结构
     */
    private class TreeNode {
        public boolean isVisited=false;
        private String data=null;
        public TreeNode leftChild=null;
        public TreeNode rightChild=null;
        private int key=0;
        private boolean rVisited=false;//该节点的左孩子是否被访问过
        public TreeNode(int key,String data){
            this.key=key;
            this.data=data;
        }
    }
}
